package algorithm.niuke;

/**
 * 二维数组查找
 * 说明：矩阵中每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序
 *
 * @author jack.wu
 * @version 1.0
 * @date 2020-05-06
 */
public class MatrixSearch {

    public static void main(String[] args) {
        int[][] matrix = {{1, 4, 8, 12},
                {2, 7, 9, 22},
                {3, 10, 17, 30}};
        int target = 15;
        boolean flag = find(matrix, target);
        System.out.println(flag);
    }

    /**
     * 查找目标数是否存在
     * 思路：
     * 利用二维数组由上到下，由左到右递增的规律，
     * 那么选取右上角或者左下角的元素a[row][col]与target进行比较，
     * 当target小于元素a[row][col]时，那么target必定在元素a所在行的左边,
     * 即col--；
     * 当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,
     * 即row++；
     *
     * @param matrix 矩阵
     * @param target 目标数
     * @return 找到返回true否者返回false
     */
    private static boolean find(int[][] matrix, int target) {

        int rowLength = matrix.length - 1;
        int row = 0;
        int col = matrix[0].length - 1;

        while (row <= rowLength && col >= 0) {
            int value = matrix[row][col];
            if (target < value) {
                col -= 1;
            } else if (target > value) {
                row += 1;
            } else {
                return true;
            }
        }
        return false;
    }
}
